class LRUCache {
public:
    LRUCache(int capacity)
        :_capacity(capacity)
    {}
    
    int get(int key) {
        auto ret=_hashmap.find(key);
        if(ret!=_hashmap.end())
        {
            LtIter it=ret->second;
            //将it对应的结点转移到链表头部
            _LRUList.splice(_LRUList.begin(),_LRUList,it);
            return it->second;
        }
        return -1;
    }
    
    void put(int key, int value) {
        auto ret=_hashmap.find(key);
        //如果找到，更新值
        if(ret!=_hashmap.end())
        {
            LtIter it=ret->second;
            it->second=value;

            //将it对应的结点转移到链表头部
            _LRUList.splice(_LRUList.begin(),_LRUList,it);
        }
        else//找不到，插入
        {
            //如果满了需要先删除最久未使用的值
            if(_capacity==_hashmap.size())
            {
                pair<int,int> back=_LRUList.back();
                _hashmap.erase(back.first);
                _LRUList.pop_back();
            }
            //插入
            _LRUList.push_front(make_pair(key,value));
            _hashmap[key]=_LRUList.begin();
        }
    }
private:
    typedef list<pair<int,int>>::iterator LtIter;

    //hash做到查找更新/插入是O(1)
    unordered_map<int, LtIter> _hashmap;

    //LRU 默认链表尾部的是最久未被使用的
    list<pair<int, int>> _LRUList;

    size_t _capacity;
};
